package com.qrpcw.algorithms;
import java.util.Arrays;
import java.util.Random;

public class MergeSort {
	
    /**
     * Merges two adjacent subranges of an array
     * @param A the array with entries to be merged
     * @param p the index of the first element of the first range
     * @param q the index of the last element of the first range
     * @param r the index of the last element of the second range
     */
	public void merge(int[] A, int p, int q, int r){
		int n1 = q - p + 1; //length n1 of the subarray A[p..q]
		int n2 = r - q;     //length n2 of the subarray A[q+1..r]
		int[] L = new int[n1+1];  
		//the extra position will hold the sentinel
		int[] R = new int[n2+1];
		for(int i=0; i<n1; i++){ L[i] = A[p+i];}
		//copies the subarray A[p..q] into L[1..n1]
		for(int j=0; j<n2; j++){ R[j] = A[(q+1)+j];}
		//copies the subarray A[q+1..r] into R[1..n2]
		int MAXVALUE = 10000;
		L[n1] = MAXVALUE;
		R[n2] = MAXVALUE;
		int i=0,j=0;
		int k;
		for(k = p; k <= r; k++){
			if(L[i]<=R[j]){
				A[k] = L[i];
				i++;
			}else{
				A[k] = R[j];
				j++;
			}
		}
	}
	
	public void mergeSort(int[] A, int p, int r){
        int q;
        if (p < r){
        q = (p + r) / 2; 
        mergeSort(A, p, q);
        mergeSort(A, q + 1, r);
        merge(A, p, q, r);
        }
	}
	
	public void sort(int[] a){  
		mergeSort(a, 0, a.length - 1);
	}
	
	private int[] generateRandomNumbers(int n){
		int[] result = new int[n];	    
		Random random = new Random();	    
		for (int i = 0; i < result.length; i++){		    
			result[i] = random.nextInt(n * 10);	    
		}	    
		return result;	
	}
	
	public static void main(String[] args) {
        MergeSort test = new MergeSort();
        int[] rad = test.generateRandomNumbers(32);
        //int[] input = { 2,1,4,6,7,23,11,9};
        test.sort(rad);
        System.out.println(Arrays.toString(rad));
	}
}


